package org.example;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Test3 {
    //leetcode 117 填充每个结点的下一个右侧结点指针II https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/

    /**
     * 通过将层序遍历的结果记录下来，然后遍历层序遍历的结果将next指针进行连接，这个过程需要多遍历一遍层序遍历的结果
     * @param root
     * @return
     */
    public Node connect1(Node root) {
        if (root == null) return root;
        List<List<Node>> list = new ArrayList<>();
        Deque<Node> deque = new ArrayDeque<>();
        deque.add(root);
        while (!deque.isEmpty()) {
            int count = deque.size();
            List<Node> l = new ArrayList<>();
            while (count > 0) {
                Node tmp = deque.poll();
                if (tmp.left != null) deque.add(tmp.left);
                if (tmp.right != null) deque.add(tmp.right);
                l.add(tmp);
                count--;
            }
            list.add(l);
        }
        for (List<Node> l1 : list) {
            for (int i = 0; i < l1.size() - 1; i++) {
                l1.get(i).next = l1.get(i + 1);
            }
            l1.get(l1.size() - 1).next = null;
        }
        return root;
    }

    /**
     * 这个方法通过prev变量来记录层序遍历的上一个结点，当遍历到下一个结点的时候，就将prev结点的next指针进行赋值
     * @param root
     * @return
     */
    public Node connect(Node root) {
        if (root == null) return root;
        Deque<Node> deque = new ArrayDeque<>();
        deque.add(root);
        while (!deque.isEmpty()) {
            int count = deque.size();
            Node prev = null;
            while (count > 0) {
                Node node = deque.poll();
                if (node.left != null) {
                    deque.add(node.left);
                    if (prev != null) {
                        prev.next = node.left;
                    }
                    prev = node.left;
                }
                if (node.right != null) {
                    deque.add(node.right);
                    if (prev != null) {
                        prev.next = node.right;
                    }
                    prev = node.right;
                }
                count--;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        Node d = new Node(4);
        Node e = new Node(5);
        Node f = new Node(7);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        Test3 test3 = new Test3();
        test3.connect(a);
        System.out.println(666);
    }
}
